package leetcode.offer;

import leetcode.base.TreeNode;

import java.util.ArrayList;

/**
 * ClassName: Offer68II_LowestCommonAncestor
 * Description: leetcode-剑指offer 68 - II 二叉树的最近公共祖先
 * date: 2021-11-14 22:07
 *
 * @author liyifan
 */
public class Offer68II_LowestCommonAncestor {
    //todo:看这块
    private TreeNode ans;

    {
        this.ans = null;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }

}
